
class Solution {
 public:
  vector<string> binaryTreePaths(TreeNode* root) {
    vector<string> result;
    vector<int> path;
    if (!root) return result;
    backtracking(root, result, path);
    return result;
  }
  void backtracking(TreeNode* cur, vector<string>& result, vector<int>& path) {
    path.push_back(cur->val);
    // 这才到了叶子节点
    if (cur->left == NULL && cur->right == NULL) {
      string sPath;
      for (int i = 0; i < path.size() - 1; i++) {
        sPath += to_string(path[i]);
        sPath += "->";
      }
      sPath += to_string(path[path.size() - 1]);
      result.push_back(sPath);
      return;
    }
    if (cur->left) {
      backtracking(cur->left, result, path);
      path.pop_back();  // 回溯
    }
    if (cur->right) {
      backtracking(cur->right, result, path);
      path.pop_back();  // 回溯
    }
  }
};

/*
class Solution {
private:
    void traversal(TreeNode* cur, string path, vector<string>& result) {
        path += to_string(cur->val); // 中
        if (cur->left == NULL && cur->right == NULL) {
            result.push_back(path);
            return;
        }
        if (cur->left) traversal(cur->left, path + "->", result); // 左
回溯就隐藏在这里 if (cur->right) traversal(cur->right, path + "->", result); //
右 回溯就隐藏在这里
    }

public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        string path;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }
};
*/